# -*- coding:utf-8 -*-
List = list

# 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
# 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

# 示例:
# board =
# [
#   ['A','B','C','E'],
#   ['S','F','C','S'],
#   ['A','D','E','E']
# ]
# 给定 word = "ABCCED", 返回 true
# 给定 word = "SEE", 返回 true
# 给定 word = "ABCB", 返回 false

# 提示：
# board 和 word 中只包含大写和小写英文字母。
# 1 <= board.length <= 200
# 1 <= board[i].length <= 200
# 1 <= word.length <= 10^3

# class Solution:
#     def exist(self, board: List[List[str]], word: str) -> bool:
#         maxlen = 10 ** 3
#         if len(word) > len(board) * len(board[0]):
#             return False
#         map = [[0 for i in range(len(board[0]))] for j in range(len(board))]
#         for i in range(len(word)):
#             c = word[len(word) - i -1]
#             isFind = False
#             for row in range(len(board)):
#                 for col in range(len(board[0])):
#                     if board[row][col] != c:
#                         continue
#                     if row - 1 >= 0 and map[row - 1][col] % maxlen == i:
#                         map[row][col] += (i + 1) * maxlen
#                         isFind = True
#                         continue
#                     if row + 1 < len(board) and map[row + 1][col] % maxlen == i:
#                         map[row][col] += (i + 1) * maxlen
#                         isFind = True
#                         continue
#                     if col - 1 >= 0 and map[row][col - 1] % maxlen == i:
#                         map[row][col] += (i + 1) * maxlen
#                         isFind = True
#                         continue
#                     if col + 1 < len(board[0]) and map[row][col + 1] % maxlen == i:
#                         map[row][col] += (i + 1) * maxlen
#                         isFind = True            
#                         continue
#             if not isFind:
#                 return False
#             for row in range(len(board)):
#                 for col in range(len(board[0])):
#                     if map[row][col] >= maxlen:
#                         map[row][col] = map[row][col] // maxlen
#             print(map)
#         return True

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rowCnt, colCnt = len(board), len(board[0])
        map = [[False] * colCnt for i in range(rowCnt)]
        
        def find(row, col, index):
            if index >= len(word):
                return True
            if board[row][col] != word[index]:
                return False
            if map[row][col]:
                return False
            map[row][col] = True
            if index + 1 >= len(word):
                return True
            if row - 1 >= 0 and find(row - 1, col, index + 1):
                return True
            if row + 1 < rowCnt and find(row + 1, col, index + 1):
                return True
            if col - 1 >= 0 and find(row, col - 1, index + 1):
                return True
            if col + 1 < colCnt and find(row, col + 1, index + 1):
                return True
            map[row][col] = False
            return False
        
        for r in range(rowCnt):
            for c in range(colCnt):
                if find(r, c, 0):
                    return True
                
        return False

t = Solution()
# print(t.exist(
#     [
#         ['A','B','C','E'],
#         ['S','F','C','S'],
#         ['A','D','E','E']
#     ], "ASAS"
# ))

print(t.exist(
    [
        ['A', 'B'],
    ], "BA"
))
